443 - Humble numbers/443.cpp

   1 #include <iostream>
   2 #include <queue>
   3
   4 using namespace std;
   5
   6 typedef unsigned long long ull;
   7
   8 ull h[5843];
   9
  10 priority_queue<ull, vector<ull>, greater<ull> > q;
  11
  12 int main(){
  13
  14   q.push(1);
  15   int i=1;
  16   while (i <= 5842){
  17     ull top = q.top();
  18     q.pop();
  19     h[i++] = top;
  20
  21     q.push(top*2);
  22     if (top % 2 != 0) {
  23       q.push(top*3);
  24     }
  25     if (top % 2 != 0 && top % 3 != 0){
  26       q.push(top*5);
  27     }
  28     if (top % 2 != 0 && top % 3 != 0 && top % 5 != 0){
  29       q.push(top*7);
  30     }
  31   }
  32
  33   int n;
  34   while ((cin >> n) && (n > 0)){
  35     printf("The ");
  36     cout << n;
  37     switch(n % 100){
  38     case 11:
  39     case 12:
  40     case 13:
  41       printf("th");
  42       break;
  43     default:
  44       switch(n % 10){
  45       case 1:
  46         printf("st");
  47         break;
  48       case 2:
  49         printf("nd");
  50         break;
  51       case 3:
  52         printf("rd");
  53         break;
  54       default:
  55         printf("th");
  56         break;
  57       }
  58     }
  59     printf(" humble number is ");
  60     cout << h[n] << ".\n";
  61   }
  62   return 0;
  63 }